INDICE
    TEMA 5.-LEMA DE BOMBEO PARA  LENGUAJES REGULARES:
DEFINICIÓN
EJEMPLOS QUE NO CUMPLEN EL LEMA
EJEMPLOS QUE SI CUMPLEN EL LEMA
 
 
El lema de bombeo se usa para demostrar que un Lenguaje No es Regular,  es decir,    que no puede ser aceptado, ese lenguaje, por un autómata finito determinístico.
DEFINICIÓN:
Sea L un conjunto regular, entonces existe un n∈ N tal que ∀ z∈ L, si |z|=n, entonces z se puede expresar de la forma z = uvw donde:
                 |uv|≤ n
|v|=1
∀ i ≥0 uviw∈ L
además n puede ser el número de estados de cualquier autómata que acepte el lenguaje L.
IMPORTANTE:
El lema de bombeo es útil para demostrar que un determinado lenguaje no es regular ( no se puede decir nada si se cumple el lema de Bombeo). Para ello hay que probar que no se verifica el lema de bombeo; es decir :
Si no se cumple el Lema ⇒ el lenguaje No es Regular.
Si se cumple el Lema ⇒ no podemos decir que el Lenguaje es Regular sólo que No es Regular, ya que el lema es una condición necesaria para que un lenguaje sea regular pero no suficiente.
Para demostrar que un lenguaje es Regular (vemos que cumple Lema de Bombeo) como no es condición suficiente para afirmar que es regular entonces buscamos el AFD o Expresión Regular o Gramática Regular que si lo demuestran en realidad.
 
PASOS QUE HAY QUE DAR PARA DEMOSTRAR QUE UN LENGUAJE DADO NO ES REGULAR:
  • Suponer un n∈ N arbitrario, que se supone que cumple las condiciones del lema.  
    •
  • Encontrar una palabra que puede depender de n, de longitud mayor o igual que n para la que sea imposible encontrar una partición como la del lema. Para demostrar que una palabra z no cumple las condiciones del lema lo que hay que hacer es:  
    •
  • Suponer una partición arbitraria de x, x=uvw tal que |uv|≤n, |v|=1  
    •
  • Encontrar un i∈ N tal que uviw∉ L 
    •
 


EJEMPLOS QUE NO CUMPLEN LAS CONDICIONES DEL LEMA DE BOMBEO PARA LENGUAJES REGULARES:

1.- Demostrar que el lenguaje L={0k1k /k=0} no es regular.



 
 

  2.- Demostrar que L={0i2 /i>=0} es un lenguaje no regular.



 
 

 


3.- Determinar si es regular o no el siguiente lenguaje L={uu` /u∈ {a,b}*} u` se obtiene a partir de u sustituyendo a por b y b por a. Ejemplo; u=aab y u`=bba entonces uu`= aabbba será una cadena válida.

 
   

EJEMPLOS QUE SI CUMPLEN LAS CONDICIONES DEL LEMA DE BOMBEO PARA LENGUAJES REGULARES.

1.- Sea L={u∈ {0,1}* / N1(u)=2n+1 n∈ N} L es regular usando el Lema de Bombeo si $ n " z z=u2n+1 ∈ L se debe cumplir que: